home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 248_01 / matches.c < prev    next >
Text File  |  1989-08-16  |  12KB  |  487 lines
  1. /*
  2. **    name:        matches.c
  3. **    purpose:    Words that almost match pattern searching
  4. **    source:        Computer Language - November 1986
  5. **            by Dave Taylor
  6. **    coded:        1988.11.07 - Roberto Artigas Jr
  7. **    NOTES:        This set of routines comes from a number of
  8. **            sources, all I did is integrate them into a
  9. **            subroutine that uses all the methods for
  10. **            text matches.
  11. */
  12. #define    DEBUG    0    /* 0 = NO debug, 1 = YES debug */
  13. #define    TEST    0    /* 0 = library, 1 = mainline test */
  14.  
  15. #include    <stdio.h>
  16. #include    <stdlib.h>
  17. #include    <ctype.h>
  18. #include    <string.h>
  19.  
  20. #ifdef    tolower
  21. #undef    tolower
  22. #endif
  23. #define    tolower(c)    (isupper(c) ? c - 'A' + 'a' : c)
  24. #ifdef    min
  25. #undef    min
  26. #endif
  27. #define    min(a,b)    ((a) < (b) ? (a) : (b))
  28.  
  29. /*
  30. **    Defined constants
  31. */
  32. #define    WORD_LENGTH    40
  33. #define    THRESHOLD    0.500    /* PF474 */
  34. #define    THRESHOLD2    0.750    /* GESTALT */
  35. #define    SOUNDEX_LENGTH    4    /* soundex */
  36. #ifndef    TRUE
  37. #define    TRUE        1
  38. #define    FALSE        0
  39. #endif
  40. /*
  41. **    For the soundex algorithm: 'x' means 'delete this letter'
  42. */
  43. #define    index_of(ch)    (ch - 'A')
  44. #define    IGNORE        'x'
  45. static    char soundex_mappings[] = { "x123x12xx22455x12623x1x2x2" };
  46. /*
  47. **    Routine prototypes
  48. */
  49. char    *remove_duplicate_letters();
  50. char    *translate_case();
  51. char    *soundex_translation_of();
  52. char    *reverse();
  53. double    pf474_algorithm();
  54.  
  55.  
  56. /*
  57. **    name:        reverse
  58. **    purpose:    Reverse the word and return it
  59. */
  60. char    *reverse(word)
  61. char    *word;
  62. {
  63.     static char    buffer[WORD_LENGTH];
  64.     register int    i, j = 0;
  65.     for (i=strlen(word)-1; i > -1; i--)
  66.         buffer[j++] = word[i];
  67.     buffer[j] = '\0';
  68.     return((char *)buffer);
  69. }
  70.  
  71.  
  72. /*
  73. **    name:        translate_case
  74. **    purpose:    Destructively translate the word to all lowercase
  75. **            returning both the altered word and a pointer to
  76. **            the altered word
  77. */
  78. char    *translate_case(word)
  79. char    *word;
  80. {
  81.     register int    index;
  82.     for (index = 0; index < strlen(word); index++)
  83.         word[index] = tolower(word[index]);
  84.     return((char *)word);
  85. }
  86.  
  87. /*
  88. **    name:        remove_duplicate_letters
  89. **    purpose:    This routine removes all multiply occurring
  90. **            letters in the given word and returns a
  91. **            'sanitized' version of the word. For example,
  92. **            given 'missionary' it returns 'misionary'.
  93. */
  94. char    *remove_duplicate_letters(word)
  95. char    *word;
  96. {
  97.     register int    index, bindex = 0;
  98.     static char    buffer[WORD_LENGTH] = { "" };
  99.     buffer[bindex++] = word[0];
  100.     for (index = 1; index < strlen(word); index++)
  101.         if (word[index-1] != word[index])
  102.             buffer[bindex++] = word[index];
  103.     buffer[bindex] = 0;
  104.     return((char *)buffer);
  105. }
  106.  
  107.  
  108. /*
  109. **    name:        check_transpositions
  110. **    purpose:    Transposes character pairs in word to see if
  111. **            any match the given patter. Returns TRUE if
  112. **            so, FALSE if not
  113. */
  114. int    check_transpositions(word,pattern)
  115. char    *word;
  116. char    *pattern;
  117. {
  118.     register int    index;
  119.     char        spare_character;
  120.     for (index=1; index < strlen(word); index++) {
  121.         spare_character = word[index];
  122.         word[index] = word[index-1];
  123.         word[index-1] = spare_character;
  124.         if (strcmp(word,pattern) == 0)
  125.             return(TRUE);
  126.         word[index-1] = word[index];
  127.         word[index] = spare_character;
  128.     }
  129.     return(FALSE);
  130. }
  131.  
  132. /*
  133. **    name:        allow_a_missing_character
  134. **    purpose:    This routine returns TRUE if word is the
  135. **            same as pattern, just missing a single letter.
  136. **    1988.10.07    Roberto Artigas Jr - If word and pattern
  137. **            is a length of one and not an exact match exit
  138. **            saying that it is false
  139. */
  140. int    allow_a_missing_character(word, pattern)
  141. char    *word;
  142. char    *pattern;
  143. {
  144.     register int    index, windex = 0;
  145.     if ((strlen(word)==1) && (strlen(pattern)==1) && (*word != *pattern))
  146.         return(FALSE);
  147.     if (strlen(word) + 1 != strlen(pattern))
  148.         return(FALSE);
  149.     for (index=0, windex=0; index < strlen(pattern); index++)
  150.         if (word[windex] == pattern[index])
  151.             windex++;
  152.         else if (windex < index)
  153.             return(FALSE);
  154.     if (word[windex] == pattern[index])
  155.          return(TRUE);
  156.     else
  157.         return(FALSE);
  158. }
  159.  
  160. /*
  161. **    name:        allow_an_incorrect_character
  162. **    purpose:    This routine returns TRUE if word is the same
  163. **            as pattern, just with a single incorrect letter.
  164. **    1988.10.07    Roberto Artigas Jr - If word and pattern
  165. **            is a length of one and not an exact match exit
  166. **            saying that it is false
  167. */
  168. int    allow_an_incorrect_character(word,pattern)
  169. char    *word;
  170. char    *pattern;
  171. {
  172.     register int    index, windex;
  173.     register int    already_seen_bad_letter = FALSE;
  174.     if (strlen(word) != strlen(pattern))
  175.         return(FALSE);
  176.     if ((strlen(word)==1) && (strlen(pattern)==1) && (*word != *pattern))
  177.         return(FALSE);
  178.     for (index=0, windex=0; index < strlen(pattern); index++) {
  179.         if (word[windex] == pattern[index])
  180.             windex++;
  181.         else if (already_seen_bad_letter)
  182.             return(FALSE);
  183.         else {
  184.             already_seen_bad_letter++;
  185.             windex++;
  186.         }
  187.     }
  188.     return(TRUE);
  189. }
  190.  
  191. /*
  192. **    name:        soundex_translation_of
  193. **    purpose:    Implement soundex algorithm tranlation
  194. */
  195. char    *soundex_translation_of(buffer)
  196. char    *buffer;
  197. {
  198.     static char    result[WORD_LENGTH];
  199.     register int    i, j, ch, newch;
  200.     result[0] = toupper(buffer[0]);
  201.     result[1] = result[2] = result[3] = '0';
  202.     result[4] = '\0';
  203.     for (i=1, j=1; i < strlen(buffer) && j < SOUNDEX_LENGTH; i++) {
  204.         ch = toupper(buffer[i]);
  205.         if ((newch = soundex_mappings[index_of(ch)]) != IGNORE)
  206.             if (result[j-1] != (char)newch)
  207.                 if (!(j == 1 && ch == result[0]))
  208.                     result[j++] = (char)newch;
  209.     }
  210.     return((char *)result);
  211. }
  212.  
  213. /*
  214. **    name:        soundex
  215. **    puspose:    Implements matching based on the soundex
  216. **            algorithm - this simple part gets the two
  217. **            words 'Soundex'ized then returns a nonzero
  218. **            if the two match on this technique.
  219. */
  220. int    soundex(word,pattern)
  221. char    *word;
  222. char    *pattern;
  223. {
  224.     char        word2[WORD_LENGTH];
  225.     char        pattern2[WORD_LENGTH];
  226.     strcpy(word2,soundex_translation_of(word));
  227.     strcpy(pattern2,soundex_translation_of(pattern2));
  228.     return((strcmp(word2,pattern2)==0));
  229. }
  230.  
  231. /*
  232. **    name:        proximity_value
  233. **    purpose:    This actually implements the algorithm used
  234. **            in the PF474 pattern matching chip from
  235. **            Proximity technologies, returning the number
  236. **            of matches encountered.
  237. */
  238. int    proximity_value(word,pattern)
  239. char    *word;
  240. char    *pattern;
  241. {
  242.     int    matches = 0, count = 1;
  243.     int    iteration, index, len;
  244.     if (strcmp(word,pattern) == 0) {
  245.         for (count=0; count <= strlen(word); count++)
  246.             matches += (2*count);
  247.         return(matches);
  248.     }
  249.      len = min(strlen(word),strlen(pattern)) + 1;
  250.     count =1;
  251.     do {
  252.     for (iteration=1; iteration<len; iteration++)
  253.         for (index=0; index<iteration; index++)
  254.             if (tolower(word[index]) == tolower(pattern[index]))
  255.                 matches++;
  256.         strcpy(word,reverse(word));
  257.         strcpy(pattern,reverse(pattern));
  258.     } while (count++ < 2);
  259.     return(matches);
  260. }
  261.  
  262. /*
  263. **    name:        pf474_algorithm
  264. **    purpose:    This is the top-level PF474 pattern matching
  265. **            routines. It implements the equation we are
  266. **            using
  267. */
  268. double    pf474_algorithm(word,pattern)
  269. char    *word;
  270. char    *pattern;
  271. {
  272.     if (strlen(word) == 0 && strlen(pattern) == 0)
  273.         return((double)1.0);
  274.     return((double) (proximity_value(word,pattern) /
  275.         (proximity_value(word,word)+proximity_value(pattern,pattern))));
  276. }
  277.  
  278. /*
  279. **    name:        GCsubstr
  280. **    purpose:    Recursive greatest common sub-string
  281. */
  282. int    GCsubstr(st1, end1, st2, end2)
  283. char    *st1;
  284. char    *end1;
  285. char    *st2;
  286. char    *end2;
  287. {
  288.     register char    *a1, *b1, *s1, *a2, *b2, *s2;
  289.     short        max, i;
  290.  
  291.     if (end1 <= st1)        /* s1 empty */
  292.       return (0);
  293.     if (end2 <= st2)        /* s2 empty */
  294.       return (0);
  295.     if (end1 == st1 + 1)        /* s1 has one char */
  296.       if (end2 == st2 + 1)        /* and s2 has one char */
  297.         return (0);            /* They cannot be equal */
  298.  
  299.     max = 0;
  300.     b1 = end1; b2 = end2;
  301.  
  302.     for (a1 = st1; a1 < b1; a1++)
  303.        for (a2 = st2; a2 < b2; a2++)
  304.           if (*a1 == *a2)
  305.             {            /* How long common sub-string? */
  306.         for (i = 1; a1[i] && (a1[i] == a2[i]); i++)
  307.            ;
  308.         if (i > max)
  309.           {
  310.           max = i; s1 = a1; s2 = a2;
  311.           b1 = end1 - max; b2 = end2 - max;
  312.           }
  313.         }
  314.     if (! max)
  315.       return (0);
  316.  
  317.     max += GCsubstr(s1 + max, end1, s2 + max, end2);    /* RHS */
  318.     max += GCsubstr(st1, s1, st2, s2);            /* LHS */
  319.  
  320.     return(max);
  321. }
  322.  
  323. /*
  324. **    name:        simil
  325. **    purpose:    Best guess matches
  326. **    author:        Ratcliff